package leetcode;

public class KnapsackProblem {

    public static void main(String[] args) {
        KnapsackProblem k = new KnapsackProblem();
        int arr[] = new int[]{2,2,4,6,3};
        int solution = k.solution(arr);
        System.out.println(solution);
    }

    public int solution(int[] arr){
        int res[][] = new int[arr.length][9];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < 9; j++) {
                // 每一个石头，都有可能放、也有可能不放，也就是 0，或 arr[i]
                if(i > 1 && res[i - 1][j] > 0 || j == arr[i] || j == 0){
                    int sum = calc(res[i][j], arr[i]);
                    res[i][j] = sum;
                    res[i][sum] = sum;
                }
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(res[i][j] + "  ");
            }
            System.out.println();
        }
        return 0;
    }

    private int calc(int i, int i1) {
        if(i == 0) return i1;
        if(i1 >= 9) return i1;
        if(i1 + i >= 9) return i1;
        return i + i1;
    }

}
